package leetcode.code1819;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	public int countDifferentSubsequenceGCDs(int[] nums) {
		int max = Arrays.stream(nums).max().getAsInt();
		boolean[] h = new boolean[max + 1];
		for (int num : nums) {
			h[num] = true;
		}
//		boolean[] is = new boolean[max + 1];
		int ans = 0;
		for (int i = 1; i <= max; i++) {
			int gcd = 0;
			for (int j = i; j <= max; j += i) {
				if (h[j]) {
					if (gcd == 0) {
						gcd = j;
					} else {
						gcd = gcd(gcd, j);
					}
					if (gcd == i) {
						ans++;
						break;
					}
				}
			}
		}
		return ans;

	}

	private int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	@Override
	public void debug4() {
		H.compare(5, this.countDifferentSubsequenceGCDs(H.str2array3("[6,10,3]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
